package code;


public class EditDistance {
	
	public int minDistance(String word1,String word2){
		int n=word1.length();
		int m=word2.length();
		if(n==0)	return m;
		if(m==0)	return n;
		int[][] dp=new int[n+1][m+1];
		int i,j;
		
		for(i=0;i<m+1;i++)
			dp[0][i]=i;
		for(i=0;i<n+1;i++)
			dp[i][0]=i;
		for(i=1;i<=n;i++){
			for(j=1;j<=m;j++){
//				dp[i+1][j+1]=maxDistance;
				if(word1.charAt(i-1)==word2.charAt(j-1)){
					dp[i][j]=dp[i-1][j-1];
				}else{
					dp[i][j]=getMin(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1;
				}
//				//若为插入操作
//				if(dp[i+1][j+1]>dp[i+1][j]+1){
//					dp[i+1][j+1]=dp[i+1][j]+1;
//				}
//				//若为删除操作
//				if(dp[i+1][j+1]>dp[i][j+1]+1){
//					dp[i+1][j+1]=dp[i][j+1]+1;
//				}
//				//若替换
//				if(dp[i+1][j+1]>dp[i][j]+1){
//					dp[i+1][j+1]=dp[i][j]+1;
//				}
				System.out.print(dp[i][j]+" ");
			}
			System.out.println();
		}
		return dp[n][m];
	}
	public int minDistanceII(String word1, String word2) {
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();
        
        int[][] distance = new int[word1.length() + 1][word2.length() + 1];
        
        for (int i = 0; i <= word1.length(); i++) {
            distance[i][0] = i;
        }
        
        for (int i = 0; i <= word2.length(); i++) {
            distance[0][i] = i;
        }
        
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    distance[i][j] = distance[i-1][j-1];
                } else {
                    distance[i][j] = getMin(distance[i-1][j], distance[i][j-1], distance[i-1][j-1]) + 1;
                }
            }
        }
        return distance[word1.length()][word2.length()];
    }
	public int getMin(int a,int b,int c){
		int min=a>b?b:a;
		return min<c?min:c;
	}
	public static void main(String[] args){
		EditDistance ed=new EditDistance();
		String word1="abcddffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff";
		String word2="bcaff";
		System.out.println(ed.minDistance(word1, word2));
	}

}
